package com.fantaike.algorithm.sort;

import java.util.Comparator;

/**
 * 快速排序：快速排序是冒泡排序的一种，把一个数组拆分成两个数组，一组为小于基准值一组为大于基准值。按照此方法
 * 采用递归的方式对此进行排序
 * @author jishushen
 * @create 2021-08-11 21:34
 */
public class Quick {
    /**
     * 判断v是否小于w
     * @param v
     * @param w
     * @Date: 2021/8/11 21:43
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    private static boolean less(Comparable v,Comparable w){
        return v.compareTo(w) < 0;
    }

    /**
     * 交换数组array中索引i处和索引j处的值
     * @param array
     * @param i
     * @param j
     * @Date: 2021/8/11 21:44
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    private static void exch(Comparable[] array,int i,int j){
        Comparable temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 对数组内的元素进行排序
     * @param array
     * @Date: 2021/8/11 21:37
     * @Author: xuepeng
     * @Return 
     * @Throws 
     */
    public static void sort(Comparable[] array){
        int lo = 0;
        int hi = array.length - 1;
        sort(array,lo,hi);
    }

    /**
     * 对数组array中从索引lo处到索引hi处之间的元素进行排序
     * @param array
     * @param lo
     * @param hi
     * @Date: 2021/8/11 21:38
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    public static void sort(Comparable[] array,int lo,int hi){
        //安全校验，也是递归出口
        if (hi <= lo){
            return;
        }
        //对数组array中从索引lo处到索引hi之间的数据进行排序
        int partition = partition(array, lo, hi); //返回的是分组的分界值所在的索引，是分界值变换后的索引
        //对左子组进行有序
        sort(array,lo,partition - 1);
        //对右子组进行有序
        sort(array,partition + 1,hi);

    }

    /**
     * 对数组array中从索引lo处到索引hi之间的元素进行分组，并返回分组界限对应的索引
     * @param array
     * @param lo
     * @param hi
     * @Date: 2021/8/11 21:40
     * @Author: xuepeng
     * @Return
     * @Throws
     */
    public static int partition(Comparable[] array,int lo,int hi){
        //确定分界值
        Comparable key = array[lo];
        //定义两个指针，分别指向待切元素的最小索引处和最大索引处的下一个位置
        int left = lo;
        int right = hi + 1;
        //切分
        while (true){
            //先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止（如果比分界值大就一直找，找到了就停止或者找到最后不存在也停止）
            while (less(key,array[--right])){
                if (right == lo){
                    break;
                }
            }
            //从左往右扫描，移动指针left,找到一个比分界值大的元素，停止（如果比分界值小就一直找，找到了就停止或者找到最后不存在也停止）
            while (less(array[++left],key)){
                if (left == hi){
                    break;
                }
            }
            //判断 left>=right, 如果为true,证明元素扫描完毕，结束循环，如果不是则交换元素
            if (left >= right){
                break;
            }else {
                exch(array,left,right);
            }
        }
        //最后，要交换分界值和right处的值
        exch(array,lo,right);
        return right;
    }

}

